package sortAlgorithm;

import java.util.Arrays;

/**
 * 排序
 */
public class Sort {

    /**
     * 冒泡排序算法
     *
     * @param arr
     */
    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public void insertionSort(int[] arr) {
        int current = 0;
        for (int i = 1, j; i < arr.length; i++) {
            //将当前要比较的数组取出来
            current = arr[i];
            //将当前数字与前面的数字一一对比
            for (j = i - 1; j >= 0 && arr[j] > current; j--) {
                //前面的数字大于当前数字，则前面的数字进行右移一位
                arr[j + 1] = arr[j];
            }
            //将当前的数字插入到适合他的位置
            arr[j + 1] = current;
        }

    }

    /**
     * 归并排序
     *
     * @param arr
     */
    public void mergeSort(int[] arr) {

    }

    /**
     * 快速排序
     *
     * @param arr
     */
    public void quickSort(int[] arr) {


    }


    public void quickSortByRecursion(int[] arr, int start, int end) {

        if (start >= end) return;
        int point = partition(arr, start, end);
        //左边排序
        quickSortByRecursion(arr, start, point - 1);
        //右边排序
        quickSortByRecursion(arr, point + 1, end);

    }

    private int partition(int[] arr, int start, int end) {

        int mid = (start + end) / 2;
        swap(arr, mid, end);

        //基准值就是arr[end]了
        int i, j;
        for (i = start, j = start; j < end; j++) {
            if (arr[j] <= arr[end]) {
                //前 i 个数都小于基准值
                swap(arr, i++, j);
            }
        }
        //将基准值与第 i 个数交换
        swap(arr, i, j);

        return i;
    }

    /**
     * 将数组内的两个数字顺序互换
     *
     * @param arr 数组
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 6, 4, 9, 8};
        Sort sort = new Sort();
        System.out.println(Arrays.toString(arr));
//        sort.bubbleSort(arr);
//        System.out.println(Arrays.toString(arr));
//        sort.insertionSort(arr);
//        System.out.println(Arrays.toString(arr));

        sort.quickSortByRecursion(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }


}
